package q2171_minimumRemoval;

import java.util.Arrays;

public class Solution {
    /*
    要考察拿出最少的豆数量
    可以先对其进行排序 然后考虑：
    如果我们保持第i个位置开始所有的豆子都要一致 i前面的所有豆子都拿出
    那么此时要拿出多少豆子
    假设总数量为 sum 那么前面的豆子和为left 此时i位置数量为avg 那么后面要拿出的数量为sum - left - (long) (beans.length - i) * avg
    拿出的总数量又要加回left
    所以每次计算即为sum - (long) (beans.length - i) * avg;
     */
    public long minimumRemoval(int[] beans) {
        Arrays.sort(beans);
        long ans = Long.MAX_VALUE;
        long sum = 0;
        for (int bean : beans) sum += bean;

        for (int i = 0; i < beans.length; i++) {
            int avg = beans[i];
//            long temp = arr[i];
//            for (int j = i + 1; j < beans.length; j++) {
//                temp += beans[j] - avg;
//            }
            long take = sum - (long) (beans.length - i) * avg;

            ans = Math.min(ans, take);
        }

        return ans;
    }
}
